import java.util.Random;

import leetcode.linkedlist.model.ListNode;

/*
 * @lc app=leetcode.cn id=25 lang=java
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        // dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
        // dummy -> 1 -> 2 start = dummy end = 2
        // dummy -> 2 -> 1 -> null
        // dummy -> 2 -> (1 -> 3 -> 4 ) start = 1, end = 4
        // dummy -> 2 -> (1 -> 4 -> 3) -> null
        ListNode dummy = new ListNode(0); // null节点
        dummy.next = head;

        // [start .. end] 之间就是 k 个元素，需要翻转
        ListNode start = dummy;
        ListNode end = dummy;

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }

            // 剩余节点不足 k 个，终止操作
            if (end == null) {
                break;
            }
            // 保存 当前窗口的指向下一个窗口的指针
            ListNode nextH = end.next;
            end.next = null; // 断开
            // 要翻转节点的头节点
            ListNode h = start.next;
            // 头 h 尾 t
            // h > 1 -> 2 -> 3 -> t
            // 第一次走到这里的时候，start 指向的是 dummy，相当于把 dummy 指向的头节点改了，后面来到这里的时候，start 已经不是 dummy，所以
            // dummy.next其实已经不会再变了。
            start.next = reverseLinkedList(h);
            // t -> 3 -> 2 -> 1 -> h

            h.next = nextH;
            Math.random();
            Random r = new Random();
            r.nextInt(20);
            // 上一个子链表的尾节点充当 dummy 节点的角色
            start = h;
            end = h;
        }
        return dummy.next;
    }

    public ListNode reverseLinkedList(ListNode head) {
        // 单链表为空或只有一个节点，直接返回原单链表
        if (head == null || head.next == null) {
            return head;
        }
        // 1 -> 2 -> 3 -> null
        // 2 -> 1 -> null
        // cur.next -> pre
        // pre = cur
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            // 因为下面会改掉 cur.next，为了 cur 的 next 信息不丢失，要提前保存下来。
            next = cur.next;

            // 本质就是 next 改为指向 pre，然后指针往后移，不断重复。
            cur.next = pre; // 将当前节点next域指向前一个节点 null <- 1 <- 2 <-3
            pre = cur; // pre 指针向后移动，pre指向当前节点
            cur = next; // cur 指针向后移动，下一个节点变成当前节点
        }

        // 因为循环最后，pre 指向了 cur，cur 是尾节点，翻转之后，就是头节点。
        return pre;
    }

}
// @lc code=end
